静5青年讲座 | Approximate Counting for Spin Systems...
Approximate Counting for Spin Systems in Sub-Quadratic Time
报告人
Dr. Jiaheng Wang
University of Edinburgh
时 间
2023年9月19日 星期二 4:00pm
地 点
静园五院204
Host
孔雨晴 助理教授
Abstract
We present two approximate counting algorithms with running time for some constant and accuracy :
(1) for the hard-core model when strong spatial mixing (SSM) is sufficiently fast;
(2) for spin systems with SSM on planar graphs with quadratic growth, such as .
The latter algorithm also extends to (not necessarily planar) graphs with polynomial growth, such as , albeit with a running time of . Our technique utilizes Weitz's self-avoiding walk tree (STOC, 2006) and the recent marginal sampler of Anand and Jerrum (SIAM J. Comput., 2022).
Joint work with Konrad Anand (Queen Mary), Weiming Feng (UC Berkeley), Graham Freifeld (Edinburgh) and Heng Guo (Edinburgh). Available at arXiv:2306.14867.
Biography
Jiaheng Wang is currently a Postdoctoral Research Associate (PDRA) at the School of Informatics, University of Edinburgh. He obtained a PhD degree at the same university under the supervision of Heng Guo. Prior to that, he got a BSc degree at Peking University and was a member of the first Turing Class. He has a general interest in algorithms and complexity, with a focus on approximate counting problems.
往 期 讲 座
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”查看海报